﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Emerald
{
    public static class MoveOrdering
    {
        public static GameState[] MergeSort(GameState[] m,bool ascending)
        {
            int count = 0;
            for(int i = 0;i<m.Length;i++)
            {
                if (m[i] == null)
                    break;
                count++;
            }


            if (count <= 1)
            {
                return m;
            }

            GameState[] left, right, result;

            int middle = count / 2;
            
            left = new GameState[middle];
            right = new GameState[middle + count % 2];
            result = new GameState[count];
            
            for (int i = 0; i < middle; i++)
            {
                left[i] = m[i];
            }
            int j = 0;
            for (int i = middle; i < count; i++)
            {
                right[j] = m[i];
                j++;
            }
            
            left = MergeSort(left,ascending);
            right = MergeSort(right,ascending);

            if ((ascending && left[middle - 1].EvalValue > right[0].EvalValue) || (left[middle - 1].EvalValue < right[0].EvalValue))
            {
                result = Merge(left, right,ascending);
            }
            else
            {
                // Append left and right to result:
                for (int i = 0; i < middle; i++)
                {
                    result[i] = left[i];
                }
                j = 0;
                for (int i = middle; i < count; i++)
                {
                    result[i] = right[j];
                    j++;
                }
            }

            return result;
        }

        public static GameState[] Merge(GameState[] left, GameState[] right,bool ascending)
        {
            GameState[] result;
            result = new GameState[left.Length+right.Length];

            int i = 0, leftSize = left.Length, rightSize = right.Length;
            
            while (leftSize > 0 && rightSize > 0)
            {
                if ((ascending && left[0].EvalValue <= right[0].EvalValue) || (left[0].EvalValue >= right[0].EvalValue))
                {
                    // Append first element of the left to the result:
                    result[i] = left[0];
                    i++;
                    // Delete the appended element from the left:
                    int j = 0;
                    for (int k = 1; k < leftSize; k++)
                    {
                        left[j] = left[k];
                        j++;
                    }
                    leftSize--;
                }
                else
                {
                    // Append first element of the right to the result:
                    result[i] = right[0];
                    i++;
                    // Delete the appended element from the right:
                    int j = 0;
                    for (int k = 1; k < rightSize; k++)
                    {
                        right[j] = right[k];
                        j++;
                    }
                    rightSize--;
                }
            }
            if (leftSize > 0)
            {
                for (int j = 0; j < leftSize; j++)
                {
                    result[i] = left[j];
                    i++;
                }
            }
            else
            {
                for (int j = 0; j < rightSize; j++)
                {
                    result[i] = right[j];
                    i++;
                }
            }

            return result;
        }
    }
}
